package com.feiyu.simplesort;

/**
 * 插入排序
 *
 * @Author nanshouxiao@teacher.com.cn
 * @Date 2017-10-26 15:23
 */
public class InsertionSort extends BaseSort {
    @Override
    public int[] sort(int[] array) {
        return sort2(array);
    }

    private int[] sort1(int[] array) {
        for (int i = 1; i < array.length ; i++) {
            int lastIndex = i;
            int temp = array[i];
            for(int j = i; j > 0; j--) {
                if (array[j - 1] > temp) {
                    array[j] = array[j - 1];
                } else {
                    array[j] = temp;
                    break;
                }
            }
        }
        return array;
    }
    /**
     * 算法导论里的伪代码
     *
     * @param array
     * @return
     */
    private int[] sort2(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] < key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
        return array;
    }

}
